1. Field of the Invention
The present invention relates to a method and apparatus for detecting important sub networks in large interaction networks.
2. Description of the Related Art
In general, a single protein has a unique function, and interacts with other proteins to perform specific biological functions in a living body. Accordingly, there are complex interaction relationships between many proteins in a single cell. In addition, many proteins form a single complex to perform a unique function, such as hemoglobin or DNA replication.
Currently, Yeast Two-Hybrid that is a biological technique is used to extract protein interaction networks, and its data includes biological interaction network database (BIND), database of interacting protein (DIP) etc. In addition, a mass spectrometry can be used to identify a complex. However, these techniques are suitable for extraction of only one complex. That is, they cannot be used to detect different complexes having similar patterns present in a network.
Thus, in order to detect different complexes, the same experiment must be repeated so that the testing costs increase. In addition, these techniques can be carried out to test protein complexes alone, but cannot find out a logical protein interaction, such as a bio signal delivery pathway in protein interaction networks. The invention disclosed in the present application aims at finding such logical protein interactions.
In order to solve this problem, a sub network graph that is identical to a given network graph can be found in the entire network graph, based on a graph theory. For example, an isomorphism concordance algorithm and a sub isomorphism concordance algorithm can be used. The isomorphism concordance algorithm is used to detect a sub graph where the structure of a graph is completely identical to respective nodes, and the sub isomorphism concordance algorithm is used to detect a sub graph where the structure of a graph is completely or conceptually identical to respective nodes. However, this method cannot be used to detect various types of complexes due to limitation on expression of a graph. In addition, use of the graph theory in detecting complexes has not been made.